package leetcode.other.greedy;

import java.util.Arrays;

/**
 * @Description: https://leetcode.cn/problems/assign-cookies/
 * 假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。
 * <p>
 * 对每个孩子 i，都有一个胃口值g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；
 * 并且每块饼干 j，都有一个尺寸 s[j]。如果 s[j]>= g[i]，
 * 我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。
 * 你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
 * @Author Ammar
 * @Create 2023/7/5 09:42
 */
public class _455_分发饼干 {

    public static void main(String[] args) {
        int[] g = {10, 9, 8, 7}, s = {5, 6, 7, 8};
        System.out.println(new _455_分发饼干().findContentChildren(g, s));
    }

    public int findContentChildren(int[] g, int[] s) {
        // 贪心策略，优先选择胃口最小的小孩子
        Arrays.sort(g); // 让胃口最小的小孩子排前面
        Arrays.sort(s); // 让饼干尺寸最小的排前面
        int sIndex = 0, count = 0;
        while (sIndex < s.length && count < g.length) {
            // 剩余饼干大于等于当前胃口
            if (s[sIndex] >= g[count]) {
                count++;
            }
            sIndex++;
        }
        return count;
    }

    public int findContentChildren1(int[] g, int[] s) {
        // 贪心策略，优先选择胃口最小的小孩子
        Arrays.sort(g); // 让胃口最小的小孩子排前面
        Arrays.sort(s); // 让饼干尺寸最小的排前面
        int gIndex = 0, sIndex = 0, count = 0;
        int left = 0; // 存放饼干
        while (sIndex < s.length && gIndex < g.length) {
            // 剩余饼干大于等于当前胃口
            if (left >= g[gIndex]) {
                left = left - g[gIndex];
                gIndex++;
                count++;
            }
            // 剩余饼干+当前饼干大于等于当前胃口
            else if (left + s[sIndex] >= g[gIndex]) {
                left = left + s[sIndex] - g[gIndex];
                gIndex++;
                sIndex++;
                count++;
            }
            // 剩余饼干+当前饼干小于当前胃口
            else {
                left = left + s[sIndex];
                sIndex++;
            }
        }
        return count;
    }
}